home *** CD-ROM | disk | FTP | other *** search
/ InfoMagic Internet Tools 1993 July / Internet Tools.iso / RockRidge / mail / sendmail / sendmail-5.65c+IDA-1.4.4.1 / uiuc / malloc.c < prev    next >
Encoding:
C/C++ Source or Header  |  1989-07-27  |  9.6 KB  |  387 lines
  1. #define DEBUG
  2. #define RCHECK
  3. /*
  4.  * Copyright (c) 1983 Regents of the University of California.
  5.  * All rights reserved.  The Berkeley software License Agreement
  6.  * specifies the terms and conditions for redistribution.
  7.  */
  8.  
  9. #if defined(LIBC_SCCS) && !defined(lint)
  10. static char sccsid[] = "@(#)malloc.c    5.6 (Berkeley) 3/9/86";
  11. #endif LIBC_SCCS and not lint
  12.  
  13. /*
  14.  * malloc.c (Caltech) 2/21/82
  15.  * Chris Kingsley, kingsley@cit-20.
  16.  *
  17.  * This is a very fast storage allocator.  It allocates blocks of a small 
  18.  * number of different sizes, and keeps free lists of each size.  Blocks that
  19.  * don't exactly fit are passed up to the next larger size.  In this 
  20.  * implementation, the available sizes are 2^n-4 (or 2^n-10) bytes long.
  21.  * This is designed for use in a virtual memory environment.
  22.  */
  23.  
  24. #include <sys/types.h>
  25.  
  26. #define    NULL 0
  27.  
  28. /*
  29.  * The overhead on a block is at least 4 bytes.  When free, this space
  30.  * contains a pointer to the next free block, and the bottom two bits must
  31.  * be zero.  When in use, the first byte is set to MAGIC, and the second
  32.  * byte is the size index.  The remaining bytes are for alignment.
  33.  * If range checking is enabled then a second word holds the size of the
  34.  * requested block, less 1, rounded up to a multiple of sizeof(RMAGIC).
  35.  * The order of elements is critical: ov_magic must overlay the low order
  36.  * bits of ov_next, and ov_magic can not be a valid ov_next bit pattern.
  37.  */
  38. union    overhead {
  39.     union    overhead *ov_next;    /* when free */
  40.     struct {
  41.         u_char    ovu_magic;    /* magic number */
  42.         u_char    ovu_index;    /* bucket # */
  43. #ifdef RCHECK
  44.         u_short    ovu_rmagic;    /* range magic number */
  45.         u_int    ovu_size;    /* actual block size */
  46. #endif
  47.     } ovu;
  48. #define    ov_magic    ovu.ovu_magic
  49. #define    ov_index    ovu.ovu_index
  50. #define    ov_rmagic    ovu.ovu_rmagic
  51. #define    ov_size        ovu.ovu_size
  52. };
  53.  
  54. #define    MAGIC        0xef        /* magic # on accounting info */
  55. #define RMAGIC        0x5555        /* magic # on range info */
  56.  
  57. #ifdef RCHECK
  58. #define    RSLOP        sizeof (u_short)
  59. #else
  60. #define    RSLOP        0
  61. #endif
  62.  
  63. /*
  64.  * nextf[i] is the pointer to the next free block of size 2^(i+3).  The
  65.  * smallest allocatable block is 8 bytes.  The overhead information
  66.  * precedes the data area returned to the user.
  67.  */
  68. #define    NBUCKETS 30
  69. static    union overhead *nextf[NBUCKETS];
  70. extern    char *sbrk();
  71.  
  72. static    int pagesz;            /* page size */
  73. static    int pagebucket;            /* page size bucket */
  74.  
  75. #ifdef MSTATS
  76. /*
  77.  * nmalloc[i] is the difference between the number of mallocs and frees
  78.  * for a given block size.
  79.  */
  80. static    u_int nmalloc[NBUCKETS];
  81. #include <stdio.h>
  82. #endif
  83.  
  84. #if defined(DEBUG) || defined(RCHECK)
  85. #define    ASSERT(p)   if (!(p)) botch("p")
  86. #include <stdio.h>
  87. static
  88. botch(s)
  89.     char *s;
  90. {
  91.     fprintf(stderr, "\r\nassertion botched: %s\r\n", s);
  92.      (void) fflush(stderr);        /* just in case user buffered it */
  93.     abort();
  94. }
  95. #else
  96. #define    ASSERT(p)
  97. #endif
  98.  
  99. char *
  100. malloc(nbytes)
  101.     unsigned nbytes;
  102. {
  103.       register union overhead *op;
  104.       register int bucket;
  105.     register unsigned amt, n;
  106.  
  107.     /*
  108.      * First time malloc is called, setup page size and
  109.      * align break pointer so all data will be page aligned.
  110.      */
  111.     if (pagesz == 0) {
  112.         pagesz = n = getpagesize();
  113.         op = (union overhead *)sbrk(0);
  114.           n = n - sizeof (*op) - ((int)op & (n - 1));
  115.         if (n < 0)
  116.             n += pagesz;
  117.           if (n) {
  118.               if (sbrk(n) == (char *)-1)
  119.                 return (NULL);
  120.         }
  121.         bucket = 0;
  122.         amt = 8;
  123.         while (pagesz > amt) {
  124.             amt <<= 1;
  125.             bucket++;
  126.         }
  127.         pagebucket = bucket;
  128.     }
  129.     /*
  130.      * Convert amount of memory requested into closest block size
  131.      * stored in hash buckets which satisfies request.
  132.      * Account for space used per block for accounting.
  133.      */
  134.     if (nbytes <= (n = pagesz - sizeof (*op) - RSLOP)) {
  135. #ifndef RCHECK
  136.         amt = 8;    /* size of first bucket */
  137.         bucket = 0;
  138. #else
  139.         amt = 16;    /* size of first bucket */
  140.         bucket = 1;
  141. #endif
  142.         n = -(sizeof (*op) + RSLOP);
  143.     } else {
  144.         amt = pagesz;
  145.         bucket = pagebucket;
  146.     }
  147.     while (nbytes > amt + n) {
  148.         amt <<= 1;
  149.         if (amt == 0)
  150.             return (NULL);
  151.         bucket++;
  152.     }
  153.     /*
  154.      * If nothing in hash bucket right now,
  155.      * request more memory from the system.
  156.      */
  157.       if ((op = nextf[bucket]) == NULL) {
  158.           morecore(bucket);
  159.           if ((op = nextf[bucket]) == NULL)
  160.               return (NULL);
  161.     }
  162.     /* remove from linked list */
  163.       nextf[bucket] = op->ov_next;
  164.     op->ov_magic = MAGIC;
  165.     op->ov_index = bucket;
  166. #ifdef MSTATS
  167.       nmalloc[bucket]++;
  168. #endif
  169. #ifdef RCHECK
  170.     /*
  171.      * Record allocated size of block and
  172.      * bound space with magic numbers.
  173.      */
  174.     op->ov_size = (nbytes + RSLOP - 1) & ~(RSLOP - 1);
  175.     op->ov_rmagic = RMAGIC;
  176.       *(u_short *)((caddr_t)(op + 1) + op->ov_size) = RMAGIC;
  177. #endif
  178.       return ((char *)(op + 1));
  179. }
  180.  
  181. /*
  182.  * Allocate more memory to the indicated bucket.
  183.  */
  184. morecore(bucket)
  185.     int bucket;
  186. {
  187.       register union overhead *op;
  188.     register int sz;        /* size of desired block */
  189.       int amt;            /* amount to allocate */
  190.       int nblks;            /* how many blocks we get */
  191.  
  192.     /*
  193.      * sbrk_size <= 0 only for big, FLUFFY, requests (about
  194.      * 2^30 bytes on a VAX, I think) or for a negative arg.
  195.      */
  196.     sz = 1 << (bucket + 3);
  197. #ifdef DEBUG
  198.     ASSERT(sz > 0);
  199. #else
  200.     if (sz <= 0)
  201.         return;
  202. #endif
  203.     if (sz < pagesz) {
  204.         amt = pagesz;
  205.           nblks = amt / sz;
  206.     } else {
  207.         amt = sz + pagesz;
  208.         nblks = 1;
  209.     }
  210.     op = (union overhead *)sbrk(amt);
  211.     /* no more room! */
  212.       if ((int)op == -1)
  213.           return;
  214.     /*
  215.      * Add new memory allocated to that on
  216.      * free list for this hash bucket.
  217.      */
  218.       nextf[bucket] = op;
  219.       while (--nblks > 0) {
  220.         op->ov_next = (union overhead *)((caddr_t)op + sz);
  221.         op = (union overhead *)((caddr_t)op + sz);
  222.       }
  223. }
  224.  
  225. free(cp)
  226.     char *cp;
  227. {   
  228.       register int size;
  229.     register union overhead *op;
  230.  
  231.       if (cp == NULL)
  232.           return;
  233.     op = (union overhead *)((caddr_t)cp - sizeof (union overhead));
  234. #ifdef DEBUG
  235.       ASSERT(op->ov_magic == MAGIC);        /* make sure it was in use */
  236. #else
  237.     if (op->ov_magic != MAGIC)
  238.         return;                /* sanity */
  239. #endif
  240. #ifdef RCHECK
  241.       ASSERT(op->ov_rmagic == RMAGIC);
  242.     ASSERT(*(u_short *)((caddr_t)(op + 1) + op->ov_size) == RMAGIC);
  243. #endif
  244.       size = op->ov_index;
  245.       ASSERT(size < NBUCKETS);
  246.     op->ov_next = nextf[size];    /* also clobbers ov_magic */
  247.       nextf[size] = op;
  248. #ifdef MSTATS
  249.       nmalloc[size]--;
  250. #endif
  251. }
  252.  
  253. /*
  254.  * When a program attempts "storage compaction" as mentioned in the
  255.  * old malloc man page, it realloc's an already freed block.  Usually
  256.  * this is the last block it freed; occasionally it might be farther
  257.  * back.  We have to search all the free lists for the block in order
  258.  * to determine its bucket: 1st we make one pass thru the lists
  259.  * checking only the first block in each; if that fails we search
  260.  * ``realloc_srchlen'' blocks in each list for a match (the variable
  261.  * is extern so the caller can modify it).  If that fails we just copy
  262.  * however many bytes was given to realloc() and hope it's not huge.
  263.  */
  264. int realloc_srchlen = 4;    /* 4 should be plenty, -1 =>'s whole list */
  265.  
  266. char *
  267. realloc(cp, nbytes)
  268.     char *cp; 
  269.     unsigned nbytes;
  270. {   
  271.       register u_int onb, i;
  272.     union overhead *op;
  273.       char *res;
  274.     int was_alloced = 0;
  275.  
  276.       if (cp == NULL)
  277.           return (malloc(nbytes));
  278.     op = (union overhead *)((caddr_t)cp - sizeof (union overhead));
  279.     if (op->ov_magic == MAGIC) {
  280.         was_alloced++;
  281.         i = op->ov_index;
  282.     } else {
  283.         /*
  284.          * Already free, doing "compaction".
  285.          *
  286.          * Search for the old block of memory on the
  287.          * free list.  First, check the most common
  288.          * case (last element free'd), then (this failing)
  289.          * the last ``realloc_srchlen'' items free'd.
  290.          * If all lookups fail, then assume the size of
  291.          * the memory block being realloc'd is the
  292.          * largest possible (so that all "nbytes" of new
  293.          * memory are copied into).  Note that this could cause
  294.          * a memory fault if the old area was tiny, and the moon
  295.          * is gibbous.  However, that is very unlikely.
  296.          */
  297.         if ((i = findbucket(op, 1)) < 0 &&
  298.             (i = findbucket(op, realloc_srchlen)) < 0)
  299.             i = NBUCKETS;
  300.     }
  301.     onb = 1 << (i + 3);
  302.     if (onb < pagesz)
  303.         onb -= sizeof (*op) + RSLOP;
  304.     else
  305.         onb += pagesz - sizeof (*op) - RSLOP;
  306.     /* avoid the copy if same size block */
  307.     if (was_alloced) {
  308.         if (i) {
  309.             i = 1 << (i + 2);
  310.             if (i < pagesz)
  311.                 i -= sizeof (*op) + RSLOP;
  312.             else
  313.                 i += pagesz - sizeof (*op) - RSLOP;
  314.         }
  315.         if (nbytes <= onb && nbytes > i) {
  316. #ifdef RCHECK
  317.             op->ov_size = (nbytes + RSLOP - 1) & ~(RSLOP - 1);
  318.             *(u_short *)((caddr_t)(op + 1) + op->ov_size) = RMAGIC;
  319. #endif
  320.             return(cp);
  321.         } else
  322.             free(cp);
  323.     }
  324.       if ((res = malloc(nbytes)) == NULL)
  325.           return (NULL);
  326.       if (cp != res)        /* common optimization if "compacting" */
  327.         bcopy(cp, res, (nbytes < onb) ? nbytes : onb);
  328.       return (res);
  329. }
  330.  
  331. /*
  332.  * Search ``srchlen'' elements of each free list for a block whose
  333.  * header starts at ``freep''.  If srchlen is -1 search the whole list.
  334.  * Return bucket number, or -1 if not found.
  335.  */
  336. static
  337. findbucket(freep, srchlen)
  338.     union overhead *freep;
  339.     int srchlen;
  340. {
  341.     register union overhead *p;
  342.     register int i, j;
  343.  
  344.     for (i = 0; i < NBUCKETS; i++) {
  345.         j = 0;
  346.         for (p = nextf[i]; p && j != srchlen; p = p->ov_next) {
  347.             if (p == freep)
  348.                 return (i);
  349.             j++;
  350.         }
  351.     }
  352.     return (-1);
  353. }
  354.  
  355. #ifdef MSTATS
  356. /*
  357.  * mstats - print out statistics about malloc
  358.  * 
  359.  * Prints two lines of numbers, one showing the length of the free list
  360.  * for each size category, the second showing the number of mallocs -
  361.  * frees for each size category.
  362.  */
  363. mstats(s)
  364.     char *s;
  365. {
  366.       register int i, j;
  367.       register union overhead *p;
  368.       int totfree = 0,
  369.       totused = 0;
  370.  
  371.       fprintf(stderr, "Memory allocation statistics %s\nfree:\t", s);
  372.       for (i = 0; i < NBUCKETS; i++) {
  373.           for (j = 0, p = nextf[i]; p; p = p->ov_next, j++)
  374.               ;
  375.           fprintf(stderr, " %d", j);
  376.           totfree += j * (1 << (i + 3));
  377.       }
  378.       fprintf(stderr, "\nused:\t");
  379.       for (i = 0; i < NBUCKETS; i++) {
  380.           fprintf(stderr, " %d", nmalloc[i]);
  381.           totused += nmalloc[i] * (1 << (i + 3));
  382.       }
  383.       fprintf(stderr, "\n\tTotal in use: %d, total free: %d\n",
  384.         totused, totfree);
  385. }
  386. #endif
  387.